\section{Problema 2}

\subsection{Enunciado}

Se instalan \textit{n} rociadores en una cancha de f\'utbol de c\'esped natural de \textit{l} metros de largo y \textit{w} metros de ancho. 
Cada rociador est\'a instalado en la l\'inea horizontal del centro de la cancha. Para cada uno de los rociadores se nos dice su
posici\'on como la distancia desde el extremo izquierdo de la l\'inea central y su radio de operaci\'on. ¿Cu\'al es el n\'umero 
m\'inimo de rociadores que se deben encender para que la cancha de f\'utbol sea regada completamente? \\

La entrada consiste de varios casos que se deben procesar en lote. Para cada caso la primera l\'inea tiene los n\'umeros
$n$, $l$, $w$ y luego hay $n$ l\'ineas que tienen la posici\'on y el radio de cada rociador. La salida debe tener una l\'inea por cada
caso con el m\'inimo n\'umero de rociadores necesarios. En caso de que sea imposible regar la cancha se debe responder -1. \\

Analizar la complejidad temporal usando el modelo uniforme y expresarla en funci\'on de $w$, $n$, $l$. Se debe encontrar un
algoritmo con complejidad estrictamente menor que $O(n^{2})$.
l rectángulo

\subsection{Introducci\'on}
La posición de los rociadores y el radio de riegue definen un círculo, que no es más que el área cubierta. Como los aspersores se encuentran centrados verticalmente con respecto a la cancha, los círculos definidos por estos también. Algunos de estos círculos intersectan el borde superior e inferior de la cancha, las dos intersecciones superiores nos definen un intervalo, y las dos inferiores también; como el círculo se encuentra centrado verticalmente, ambos intervalos son iguales. Como el problema es simétrico, ya que los intervalos son iguales, podemos obviar el análisis de la mitad inferior.

Las intersecciones definen un intervalo cerrado que representa el área que el aspersor riega cubriendo completamente el ancho de la cancha. Los rociadores que no posean un intervalo asociado no lo cubren y por ende no pueden ser parte de la solución, pues no aportan nada.

\begin{center}
	\includegraphics[scale=0.5]{problema2/intervalo_representa.png}
\end{center}

%TODO: Hacer un gráfico que muestre que los aspersores que no tienen intervalo asociado no cubren la cancha en todo su anchito :-)

Si para todos los aspersores calculamos el intervalo asociado traducimos el problema a simplemente elegir la menor cantidad de intervalos de manera tal que todo la cancha quede cubierta, es decir, que la unión de todos los intervalos en la solución den como resultado un intervalo que contenga a la cancha (el intervalo $[0;l]$).

\begin{center}
	\includegraphics[scale=0.5]{problema2/circulo_a_intervalo.png}
\end{center}

Para obtener el intervalo asociado a un aspersor basta con resolver para $\frac{ancho\ del\ intervalo}{2}$ sobre el triángulo rectángulo de la figura.

$$ r^2 = \left( \frac{w}{2} \right) ^2 + \left( \frac{ancho\ del\ intervalo}{2} \right) ^2  $$
$$ \frac{ancho\ del\ intervalo}{2} = \sqrt{r^2 -  \left( \frac{w}{2} \right )^2} $$
$$ \frac{ancho\ del\ intervalo}{2} = \sqrt{r^2 -  \frac{w^2}{4} } $$


%%%%%%%%%%%%%%%%%%% EXPLICACION
Una vez que definimos el problema en base a intervalos, ordenamos la lista de intervalos de menor a mayor en base al extremo inferior. Una vez ordenados elegimos el intervalo cuyo extremo inferior sea menor o igual a 0 y cuyo extremo superior sea superior al de todos los que cumplan la primer condición. De esta manera cubrimos el área más grande desde el comienzo de la cancha que puede cubrir un único aspersor. Este intervalo lo agregamos a la solución.

Como los intervalos están ordenados continuamos a partir del último intervalo inspeccionado, buscando un intervalo cuyo extremo inferior sea menor o igual al extremo superior del último intervalo agregado a la solución, y que a su vez posea el mayor extremo superior de todos los que cumplan la primer condición. Agregamos este intervalo a la solución y repetimos este procedimiento hasta cubrir toda la cancha o quedarnos sin intervalos que cumplan las condiciones (lo cual quiere decir que no hay solución).

%%%%%%%%%%%%%%%%%%%%%%% PSEUDOCODIGO
% lista de intervalos l;
% para cada aspersor:
%    encontrar el intervalo asociado y agregarlo a l.
% 
% intervalo actual = [0;0];
% intervalo temporal = [0;0];
% solucion = 0;
% para cada intervalo i:
%    si inf(i) <= sup(actual) ^ sup(i) > sup(temporal):
%       temporal = i;
%    sino si inf(i) > sup(actual):
%      si temporal = [0;0]:
%         no tiene solución;
%      sino
%         solucion++;
%         actual = temporal;
%         repetir i en la próxima iteración;
% 


\subsection{Correctitud}
En cada iteración nuestro algoritmo elige el intervalo que intersecte con el intervalo anterior y que al mismo tiempo posea el extremo superior más grande, de esta manera nos aseguramos que el intervalo que elegimos cubra la mayor sección de cancha. Esto es óptimo porque los intervalos deben intersectarse para no dejar partes de la cancha sin cubrir, y como elegimos el que cubre la mayor sección posible sabemos que cualquier otro tendría un extremo superior menor al de este último (tendría menos ``alcance''). Si eligiésemos otro tendríamos tres posibilidades:

\begin{itemize}
 \item El aspersor no cubre lo suficiente y por ende tenemos que elegir un rociador extra (haciendo a la solución no óptima).
 \item El rociador no cubre lo suficiente y no encontramos ninguno que lo intersecte, de modo que no hay solución.
 \item El rociador cubre lo suficiente y es parte de la solución óptima, pero nuestro algoritmo eligiría un aspersor que tenga su extremo superior mayor al de este.
\end{itemize}

Entonces el algoritmo siempre encuentra una solución óptima (si la hay).
\subsection{Pseudoc\'odigo}

\begin{algorithm}[H]
\caption{apersoresMinimos(Secuencia$<$Aspersor$>$ $aspersores$, Longitud $l$, Ancho $w$)}
\begin{algorithmic}
	\STATE Secuencia$<$Intervalo$>$ $intervalos$
	
	\FOR{\textbf{cada} Aspersor $a$ \textbf{en} $aspersores$}
		\IF{$a$ no alcanza a rociar hasta $w$}
			\STATE \textbf{continuar}
		\ENDIF
		\STATE
		
		\STATE Intervalo $i \leftarrow convertirEnIntervalo(a)$
		\STATE $agregar(i, intervalos)$
	\ENDFOR
	\STATE
	
	\STATE $intervalos \leftarrow ordenarPorExtremoInferior(intervalos)$
	\STATE 
	
	\STATE $temp \leftarrow [0,0]$
	\STATE $ultimo \leftarrow [0,0]$
	\STATE $cantidad \leftarrow 0$
	
	\FOR{\textbf{cada} Intervalo $i$ \textbf{en} $intervalos$}
		\IF{$i$ intersecta a $ultimo$ \textbf{e} $i$ cubre más que $temp$}
			\STATE $temp \leftarrow i$
		\ELSE
			\IF{$i$ no intersecta a $ultimo$ \textbf{y} $temp$ intersecta a $ultimo$}
				\STATE $cantidad++$
				\STATE
				
				\IF{ya cubrimos todo $l$}
					\RETURN $cantidad$
				\ENDIF
				\STATE
				
				\STATE $ultimo \leftarrow temp$
				\STATE $temp \leftarrow i$
			\ENDIF
		\ENDIF
	\ENDFOR
	\STATE
	
	\IF{$temp$ intersecta a $ultimo$ \textbf{y} $temp$ cubre lo que falta para llegar a $l$}
		\STATE $cantidad++$
		\RETURN $cantidad$
	\ENDIF
	\STATE
	
	\RETURN $-1$
\end{algorithmic}
\end{algorithm}

\subsection{Análisis de Complejidad}
Basicamente el algoritmo se divide en 3 etapas.

\begin{enumerate}
	\item Calcular los intervalos asociados a los rociadores.
	\item Ordenar los intervalos.
	\item Seleccionar los intervalos que son parte de la solución.
\end{enumerate}

\subsubsection{Calcular intervalos}
El cálculo de un intervalo a partir de un rociador y la cancha lleva tiempo constante, es basicamente calcular $ \frac{ancho\ del\ intervalo}{2} = \sqrt{r^2 -  \frac{w^2}{4} } $. Agregarlo a la secuencia de intervalos ya calculados es una operación cuya complejidad viene definida por la elección de la estructura de datos utilizada para representar la secuencia. En la implementación utilizamos {\bf std::vector}, agregar un elemento al final del vector es una operación de tiempo constante ($O(1)$), excepto para el caso donde el vector se queda sin espacio de almacenamiento, para ese caso posee una complejidad dependiente de la cantidad de elementos en el vector ($O(n)$). Utilzando una lista ({\bf std::list}) podríamos asegurarnos que siempre se realice en tiempo constante, también podríamos hacerlo si utilizamos un vector con el espacio suficiente reservado de antemano. Sin embargo encontramos que no es esto necesario, pues agregar un elemento al final del vector es $O(n)$ en muy pocos casos, y a efectos prácticos se comporta como si fuera constante (en el análisis amortizado es $O(1)$). Si realmente fuera muy importante que {\bf siempre} fuera $O(1)$ utilizaríamos otra estructura de datos, pero nos quedamos con {\bf std::vector} porque el algoritmo de ordenación es más eficiente que el algoritmo utilizado sobre {\bf std::list} (pese a que ambos son $O(n \cdot \log~ n)$).

Como recorre todos los rociadores, calcula el intervalo asociado, y agrega el intervalo a la secuencia de intervalos (con operaciones constantes) esta primera parte del ejercicio tiene una complejidad $O(n)$.


\begin{verbatim}
int resolverProblema( const vector< Circulo > &circulos, int l, int w ) {
  vector< Intervalo > intervalos;
  int n = circulos.size();

  // Recorre n veces, entonces es O(n).
  for ( int i = 0; i < n; i++ ) {
    entero_t r = circulos[i].r;
    entero_t d = circulos[i].d;

    prec_t determinante = (r * r) - (w * w) / 4.0;
    if ( determinante <= 0.0 )
      continue;

    prec_t alcance = sqrt( determinante );
    
    // Asumimos que esta operación es O(1)
    intervalos.push_back( Intervalo( d - alcance, d + alcance ) );
  }
}
\end{verbatim}

\subsubsection{Ordenar intervalos}
Para ordenar los intervalos simplemente utilizamos la función {\bf sort} de la {\bf STL}. El algoritmo que implementa la STL es {\bf Introsort}, que tiene una complejidad $O(n \cdot \log~ n)$ tanto en el peor caso como en el caso promedio: \url{http://www.sgi.com/tech/stl/sort.html}.

\begin{verbatim}
   sort( intervalos.begin(), intervalos.end() ); // O( n log n )
\end{verbatim}

\subsubsection{Seleccionar intervalos}
Los intervalos que forman parte de la solución se seleccionan en una única pasada sobre el vector de intervalos, dado que las operaciones realizadas dentro y fuera del ciclo son constantes, esta parte del algoritmo es $O(n)$.

\begin{verbatim}
int resolver( const vector< Intervalo > &intervalos, int l ) {
  int len = intervalos.size();
  int temp = 0;
  int solucion = 0;
  prec_t ultimo = 0.0;

  // Recorremos todos los intervalos: O(len)
  for ( int i = 0; i < len; i++ ) {
    if ( intervalos[i].a <= ultimo && intervalos[i].b > intervalos[temp].b ) {
      temp = i;
    } else if ( intervalos[i].a > ultimo && intervalos[temp].a <= ultimo ) {
      solucion++;
      if ( intervalos[temp].b >= l ) return solucion;
      ultimo = intervalos[temp].b;
      temp = i;
    }
  }

  if ( temp < len && intervalos[temp].a <= ultimo && intervalos[temp].b >= l )
    return solucion + 1;
  return -1;
}
\end{verbatim}

\subsubsection{Conclusión}
Las 3 etapas del algoritmo tienen las siguientes complejidades:

\begin{enumerate}
	\item Calcular los intervalos asociados a los rociadores: $O( n )$.
	\item Ordenar los intervalos: $O( n \cdot \log~ n )$.
	\item Seleccionar los intervalos que son parte de la solución: $O( n )$.
\end{enumerate}

De modo que la complejidad del problema es $O( n + n \cdot \log~ n + n ) = O( n \cdot \log~ n )$.

\subsection{Mediciones}
Al realizar las mediciones identificamos basicamente 2 casos, el mejor y el peor. Dado que nuestro algoritmo descarta los rociadores que no pueden ser parte de la solución debido a que su radio de cobertura no llega al borde de la cancha, si ningún rociador cubre lo suficiente todos serán descartados en una única pasada por la lista de rociadores. De modo que el mejor caso es $O(n)$

\includegraphics[width=\textwidth]{problema2/mejores.png}

El peor caso se da cuando todos los rociadores son parte de la solución, de modo que no se puede descartar ninguno. Además, si los rociadores están ordenados de manera que se consiga el peor caso de Introsort (el algoritmo utilizado por la STL), obtenemos el peor caso del algoritmo. Para Introsort el peor caso se da en las secuencias ``median-of-3 killer'', pero nos alcanzó con simplemente ordenar a la inversa la lista de rociadores para obtener casos muy malos. La complejidad para el peor caso es $O(n \cdot \log~ n)$

\includegraphics[width=\textwidth]{problema2/peores.png}


En la siguiente figura se puede ver una comparación del mejor y el peor caso, además de casos aleatorios.

\includegraphics[width=\textwidth]{problema2/comparacion.png}

\newpage
